DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2021.28

Strongly Linearizable Linked List and Queue

Authors: Steven Munsu Hwang and Philipp Woelfel

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract

Strong linearizability is a correctness condition conceived to address the inadequacies of linearzability when using implemented objects in randomized algorithms. Due to its newfound nature, not many strongly linearizable implementations of data structures are known. In particular, very little is known about what can be achieved in terms of strong linearizability with strong primitives that are available in modern systems, such as the compare-and-swap (CAS) operation. This paper kick-starts the research into filling this gap. We show that Harris’s linked list and Michael and Scott’s queue, two well-known lock-free, linearizable data structures, are not strongly linearizable. In addition, we give modifications to these data structures to make them strongly linearizable while maintaining lock-freedom. The algorithms we describe are the first instances of non-trivial, strongly linearizable data structures of their type not derived by a universal construction.

Cite as

Steven Munsu Hwang and Philipp Woelfel. Strongly Linearizable Linked List and Queue. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hwang_et_al:LIPIcs.OPODIS.2021.28,
  author =	{Hwang, Steven Munsu and Woelfel, Philipp},
  title =	{{Strongly Linearizable Linked List and Queue}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.28},
  URN =		{urn:nbn:de:0030-drops-158030},
  doi =		{10.4230/LIPIcs.OPODIS.2021.28},
  annote =	{Keywords: Strong linearizability, compare-and-swap, linked list, queue, lock-freedom}
}

Search Results

Documents authored by Hwang, Steven Munsu

Strongly Linearizable Linked List and Queue

Abstract

Cite as

Thanks for your feedback!

Could not send message